package ljl.codetop300;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.TreeMap;

public class _347_top_k {

  /**
   * 对了反正
   */
  static class go {
    public int[] topKFrequent(int[] nums, int k) {
      record Node(int value, int count) {}

      Map<Integer, Integer> map = new HashMap<>();
      for (int num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
      }
      PriorityQueue<Node> q = new PriorityQueue<>(Comparator.comparingInt((Node n) -> n.count).reversed());
      map.forEach((key, v) -> {
        q.offer(new Node(key, v));
      });
      int[] res = new int[k];
      for (int i = 0; i < k; i++) {
        res[i] = q.poll().value;
      }
      return res;
    }
  }

  /**
   * 和我的思路一模一样，就是他只维护了 k 个元素
   */
  static class heap {
    public int[] topKFrequent(int[] nums, int k) {
      Map<Integer, Integer> occurrences = new HashMap<>();
      for (int num : nums) {
        occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
      }

      // int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
      PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(m -> m[1]));

      // 明明一个倒序就解决了，非要瞎搞，王八蛋
      for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
        int num = entry.getKey(), count = entry.getValue();
        if (queue.size() == k) {
          if (queue.peek()[1] < count) {
            queue.poll();
            queue.offer(new int[]{num, count});
          }
        } else {
          queue.offer(new int[]{num, count});
        }
      }

      int[] ret = new int[k];
      for (int i = 0; i < k; ++i) {
        ret[i] = queue.poll()[0];
      }
      return ret;
    }
  }

  static class quicksort {
    public int[] topKFrequent(int[] nums, int k) {
      Map<Integer, Integer> occurrences = new HashMap<>();
      for (int num : nums) {
        occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
      }
      // 获取每个数字出现次数
      List<int[]> values = new ArrayList<>();
      for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
        int num = entry.getKey(), count = entry.getValue();
        values.add(new int[]{num, count});
      }
      int[] ret = new int[k];
      qsort(values, 0, values.size() - 1, ret, 0, k);
      return ret;
    }

    public void qsort(List<int[]> values, int start, int end, int[] ret, int retIndex, int k) {
      int picked = (int) (Math.random() * (end - start + 1)) + start;
      Collections.swap(values, picked, start);

      // 让我头疼！
      int pivot = values.get(start)[1];
      int index = start;
      for (int i = start + 1; i <= end; i++) {
        if (values.get(i)[1] >= pivot) {
          Collections.swap(values, index + 1, i);
          index++;
        }
      }
      Collections.swap(values, start, index);

      if (k <= index - start) {
        // 前 k 大的值在左侧的子数组里
        qsort(values, start, index - 1, ret, retIndex, k);
      }
      else {
        // 前 k 大的值等于左侧的子数组全部元素
        // 加上右侧子数组中前 k - (index - start + 1) 大的值
        for (int i = start; i <= index; i++) {
          ret[retIndex++] = values.get(i)[0];
        }
        if (k > index - start + 1) {
          qsort(values, index + 1, end, ret, retIndex, k - (index - start + 1));
        }
      }
    }
  }

  static class copy_quicksort {
    public int[] topKFrequent(int[] nums, int k) {
      Map<Integer, Integer> map = new HashMap<>();
      for (int num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
      }
      List<int[]> list = new ArrayList<>();
      map.forEach((num, count) -> list.add(new int[] {num, count}));

      int[] res = new int[k];
      sort(list, 0, list.size() - 1, res, k);
      return res;
    }

    void sort(List<int[]> list, int start, int end, int[] res, int k) {
      int[] e = list.get(start);
      int pivot = e[1];
      int l = start, r = end;
      while (l < r) {
        while (l < r && list.get(r)[1] <= pivot) r--;
        list.set(l, list.get(r));
        while (l < r && list.get(l)[1] >= pivot) l++;
        list.set(r, list.get(l));
      }
      list.set(l, e);
      if (l - start + 1 > k) {
        sort(list, start, l - 1, res, k);
      } else {
        for (int i = start; i <= l; i++) {
          res[i] = list.get(i)[0];
        }
        if (l - start + 1 < k) {
          sort(list, l + 1, end, res, k - (l - start + 1));
        }
      }
    }
  }
}
